TNotes.leetcode

Appearance

0034. 在排序数组中查找元素的第一个和最后一个位置【中等】

0034. 在排序数组中查找元素的第一个和最后一个位置【中等】 ​

1. 📝 题目描述 ​

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

txt
输入：nums = [5, 7, 7, 8, 8, 10], target = 8
输出：[3, 4]

示例 2：

txt
输入：nums = [5, 7, 7, 8, 8, 10], target = 6
输出：[-1, -1]

示例 3：

txt
输入：nums = [], target = 0
输出：[-1, -1]

提示：

  • 0 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • nums 是一个非递减数组
  • -10^9 <= target <= 10^9

2. 🎯 s.1 - 二分查找左边界 ​

c
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
// 二分找左边界：最小的 >= t 的位置
int lowerBound(int* nums, int numsSize, int t) {
    int left = 0, right = numsSize;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < t)
            left = mid + 1;
        else
            right = mid;
    }
    return left;
}

int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
    *returnSize = 2;
    int* res = (int*)malloc(2 * sizeof(int));

    int start = lowerBound(nums, numsSize, target);
    if (start == numsSize || nums[start] != target) {
        res[0] = res[1] = -1;
        return res;
    }
    res[0] = start;
    res[1] = lowerBound(nums, numsSize, target + 1) - 1;
    return res;
}
js
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function (nums, target) {
  // 二分找左边界：最小的 >= target 的位置
  const lowerBound = (t) => {
    let left = 0,
      right = nums.length
    while (left < right) {
      const mid = (left + right) >> 1
      if (nums[mid] < t) left = mid + 1
      else right = mid
    }
    return left
  }

  const start = lowerBound(target)
  if (start === nums.length || nums[start] !== target) return [-1, -1]
  const end = lowerBound(target + 1) - 1
  return [start, end]
}
py
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # 二分找左边界：最小的 >= t 的位置
        def lower_bound(t: int) -> int:
            left, right = 0, len(nums)
            while left < right:
                mid = (left + right) >> 1
                if nums[mid] < t:
                    left = mid + 1
                else:
                    right = mid
            return left

        start = lower_bound(target)
        if start == len(nums) or nums[start] != target:
            return [-1, -1]
        return [start, lower_bound(target + 1) - 1]
  • 时间复杂度：O(log⁡n)，两次二分查找各一次
  • 空间复杂度：O(1)，只使用了常数级别的额外变量

算法思路：

  • 封装一个 lowerBound(t) 函数，返回数组中第一个大于等于 t 的元素下标（左闭右开区间 [0, n) 内二分）
  • start = lowerBound(target)
    • 直接返回 [-1, -1] 的两种情况：
    • 情况 1：所有元素都 < target，会导致越界，即 start = len(nums)
    • 情况 2：未找到目标成员 nums[start] != target
    • 在 start 合法的情况下，再继续查找 end
  • end = lowerBound(target + 1) - 1
    • target + 1 的左边界就是 target 的右边界 + 1

Discussions